#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //my ans false
    bool ans1(vector<int>& num){
        int p = 0, step;
        int length = num.size();
        int max_num = 0;
        if(length == 1){
            return true;
        }
        else{
            if(num[0] == 0){
                return false;
            }
        }
        for(int i = 0; i != length; i++){
            if(max_num < num[i]){
                max_num = num[i];
            }
            if(num[i] >= length-i-1){
                return true;
            }
            else{
                step = num[i];
                if(num[step+i] == 0){
                    p++;
                }
                else{
                    p = 0;
                }
            }
            if(num[i+1] == 0 && p >= max_num){
                return false;
                max_num = 0;
            }
            else{
                p = 0;
            }
        }
        return true;     
    }

    //贪心--记录最右侧能到的位置
    bool ans2(vector<int>& num){
        int length = num.size();
        int rightmost = 0;
        for(int i = 0; i != length; i++){
            if(i <= rightmost){
                rightmost = max(rightmost, i+num[i]);
                if(rightmost >= length-1){
                    return true;
                }
            }
        }
        return false;
    }

    // my ans true
    bool ans3(vector<int>& num){
        int p1, p2;
        int temp, max_index = 0;
        for(p1 = 0; p1 != num.size(); p1++){
            p2 = num[p1] + p1;
            max_index = max(p2, max_index);
            if(p2 >= num.size()-1){
                return true;
            }
            if(num[p1] == 0 && p1 == max_index){
                return false;
            }
        }
        return true;
    }

};

void test1(){
    vector<int> num = {2, 3, 1, 1, 4};

    Solution s;
    // bool ret = s.ans2(num);
    bool ret = s.ans3(num);
    cout << ret << endl;
}

void test2(){
    vector<int> num = {3, 2, 1, 0, 4};

    Solution s;
    // bool ret = s.ans2(num);
    bool ret = s.ans3(num);
    cout << ret << endl;
}

void test3(){
    vector<int> num = {2, 0};

    Solution s;
    // bool ret = s.ans2(num);
    bool ret = s.ans3(num);
    cout << ret << endl;
}

void test4(){
    vector<int> num = {5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0};

    Solution s;
    // bool ret = s.ans2(num);
    bool ret = s.ans3(num);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();
    test4();

    return 0;
}